package 二分查找.easy;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 1. 问题描述
 *      求出两个数组之间的交集部分
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 求出两个数组的交集2 {
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6};
        List<Integer> list = (List<Integer>) Arrays.stream(array).boxed().collect(Collectors.toList());
        Integer remove = list.remove(1);
        System.out.println(remove);
        for (Integer integer : list) {
            System.out.println(integer);
        }
        System.out.println(list.get(1));
    }

    /**
     * 用经典的二分有问题，对于重复数字不太好判别当前查询的是哪一个，可能会出现重复查询的情况
     * 所以我就换了一个方式，没有用二分，时间复杂度和空间复杂度都比较高
     * 1. 使用两个hashmap分别存放两个数组 key为元素 value为该元素在各自数组中出现的次数
     * 2. 额外使用一个容器ArrayList来存放相交的元素
     * 3. 注意此时我们扫描其中一个map，而不是数组，因为数组中存在重复元素
     *      当前map的key如果出现在另外一个map中，说明该key为重复元素，我们需要
     *      取出两个map对应的value，即该元素在两个数组中出现的次数，我们选择最少
     *      的一个，将key重复存入容器内
     * 4. 在创建一个int数组。这是最终返回的结果
     *
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        ArrayList<Integer> contains = new ArrayList<>(); // 存放相交元素
        Map<Integer,Integer> map1 = new HashMap<>();
        Map<Integer,Integer> map2 = new HashMap<>();
        for(int i = 0; i < nums1.length; i++) {
            map1.put(nums1[i],(map1.containsKey(nums1[i])) ? map1.get(nums1[i])+1 : 1);
        }
        for(int i = 0; i < nums2.length; i++) {
            map2.put(nums2[i],(map2.containsKey(nums2[i])) ? map2.get(nums2[i])+1 : 1);
        }
        for(int key : map1.keySet()) {
            if(map2.containsKey(key)) {
                int min = Math.min(map1.get(key),map2.get(key));
                while(min > 0) {
                    contains.add(key);
                    min--;
                }
            }
        }
        int[] ans = new int[contains.size()];
        for(int i = 0; i < contains.size(); i++) {
            ans[i] = contains.get(i);
        }
        return ans;
    }
}
